{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Powerful Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: powerfulIntegers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #强整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定三个整数 <code>x</code>&nbsp;、&nbsp;<code>y</code>&nbsp;和<em>&nbsp;</em><code>bound</code><em>&nbsp;</em>，返回 <em>值小于或等于&nbsp;<code>bound</code>&nbsp;的所有&nbsp;<strong>强整数</strong>&nbsp;组成的列表</em>&nbsp;。</p>\n",
    "\n",
    "<p>如果某一整数可以表示为&nbsp;<code>x<sup>i</sup>&nbsp;+ y<sup>j</sup></code>&nbsp;，其中整数&nbsp;<code>i &gt;= 0</code> 且&nbsp;<code>j &gt;= 0</code>，那么我们认为该整数是一个&nbsp;<strong>强整数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>你可以按 <strong>任何顺序</strong> 返回答案。在你的回答中，每个值 <strong>最多</strong> 出现一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2, y = 3, bound = 10\n",
    "<strong>输出：</strong>[2,3,4,5,7,9,10]\n",
    "<strong>解释： </strong>\n",
    "2 = 2<sup>0</sup> + 3<sup>0</sup>\n",
    "3 = 2<sup>1</sup> + 3<sup>0</sup>\n",
    "4 = 2<sup>0</sup> + 3<sup>1</sup>\n",
    "5 = 2<sup>1</sup> + 3<sup>1</sup>\n",
    "7 = 2<sup>2</sup> + 3<sup>1</sup>\n",
    "9 = 2<sup>3</sup> + 3<sup>0</sup>\n",
    "10 = 2<sup>0</sup> + 3<sup>2</sup></pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 3, y = 5, bound = 15\n",
    "<strong>输出：</strong>[2,4,6,8,10,14]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= x, y &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= bound &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [powerful-integers](https://leetcode.cn/problems/powerful-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [powerful-integers](https://leetcode.cn/problems/powerful-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3\\n10', '3\\n5\\n15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "            x_acc = 1\n",
    "            y_acc = 1\n",
    "            ans = []\n",
    "            while x_acc <= bound:\n",
    "                while y_acc <= bound - x_acc:\n",
    "                     ans.append(x_acc + y_acc)\n",
    "                     y_acc *=  y    \n",
    "                     if y == 1:\n",
    "                         break                 \n",
    "                y_acc = 1\n",
    "                if x == 1:\n",
    "                    break\n",
    "                x_acc *= x \n",
    "            \n",
    "            return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int):\n",
    "        x_power_list = [1]\n",
    "        while x_power_list[-1] < bound:\n",
    "            if x == 1:\n",
    "                break\n",
    "            cof = len(x_power_list)\n",
    "            x_power_list.append(x**cof)\n",
    "\n",
    "        y_power_list = [1]\n",
    "        while y_power_list[-1] < bound:\n",
    "            if y == 1:\n",
    "                break\n",
    "            cof = len(y_power_list)\n",
    "            y_power_list.append(y**cof)\n",
    "\n",
    "        result = []\n",
    "        for i in range(len(x_power_list)):\n",
    "            for j in range(len(y_power_list)):\n",
    "                temp = x_power_list[i] + y_power_list[j]\n",
    "                if temp <= bound:\n",
    "                    result.append(temp)\n",
    "\n",
    "        return list(set(result))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        lst=[]\n",
    "\n",
    "        \n",
    "        for i in range(20):\n",
    "            for j in range(20):\n",
    "                n = x**i+y**j\n",
    "                if n<=bound :\n",
    "                    lst.append(n)\n",
    "        return list(set(lst))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound < 2:\n",
    "            return []\n",
    "        ans = set()\n",
    "        bx = 1 if x == 1 else ceil(log(bound, x))\n",
    "        by = 1 if y == 1 else ceil(log(bound, y))\n",
    "        for i in range(bx):\n",
    "            for j in range(by):\n",
    "                t = x ** i + y ** j\n",
    "                if t <= bound:\n",
    "                    ans.add(t)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if x == y == 1: return [2] if 2 <= bound else []\n",
    "        if x < y: x, y = y, x\n",
    "        ans = set()\n",
    "        val, mul = 2, 1\n",
    "        while val <= bound:\n",
    "            ans.add(val)\n",
    "            mul *= x\n",
    "            val = mul + 1\n",
    "        if y != 1:\n",
    "            tem = list(ans)\n",
    "            for t in tem:\n",
    "                base, mul = t-1, y\n",
    "                val = base + mul\n",
    "                while val <= bound:\n",
    "                    ans.add(val)\n",
    "                    mul *= y\n",
    "                    val = mul + base\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = []\n",
    "        if x == 1 and y == 1:\n",
    "            if bound >= 2:\n",
    "                return [2]\n",
    "            else:\n",
    "                return res\n",
    "        if x == 1 or y == 1:\n",
    "            if x == 1:\n",
    "                l = 0\n",
    "                while 1:\n",
    "                    n = y ** l + 1\n",
    "                    if n > bound:\n",
    "                        break\n",
    "                    if n not in res:\n",
    "                        res.append(n)\n",
    "                    l += 1\n",
    "            else:\n",
    "                l = 0\n",
    "                while 1:\n",
    "                    n = x ** l + 1\n",
    "                    print(n)\n",
    "                    if n > bound:\n",
    "                        break\n",
    "                    if n not in res:\n",
    "                        res.append(n)\n",
    "                    l += 1\n",
    "            return res\n",
    "        a = 0\n",
    "        while 1:\n",
    "            if x ** a > bound:\n",
    "                break\n",
    "            b = 0\n",
    "            while 1:\n",
    "                n = x ** a + y ** b\n",
    "                if n > bound:\n",
    "                    break\n",
    "                if n not in res:\n",
    "                    res.append(n)\n",
    "                b += 1\n",
    "            a += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        value1 = 1\n",
    "        for i in range(21):\n",
    "            value2 = 1\n",
    "            for j in range(21):\n",
    "                value = value1 + value2\n",
    "                if value <= bound:\n",
    "                    res.add(value)\n",
    "                else:\n",
    "                    break\n",
    "                value2 *= y\n",
    "            if value1 > bound:\n",
    "                break\n",
    "            value1 *= x\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        i = 0\n",
    "        while True:\n",
    "            first = x ** i\n",
    "            if first > bound:\n",
    "                break\n",
    "            j = 0\n",
    "            while True:\n",
    "                second = y ** j\n",
    "                s = first + second\n",
    "                if s > bound:\n",
    "                    break\n",
    "                res.add(s)\n",
    "                if y == 1:\n",
    "                    break\n",
    "                j += 1\n",
    "            if x == 1:\n",
    "                break\n",
    "            i += 1\n",
    "        return list(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\r\n",
    "        ans = set()\r\n",
    "        for i in range(30):\r\n",
    "            xx = x**i\r\n",
    "            if xx > bound:\r\n",
    "                break\r\n",
    "            for j in range(30):\r\n",
    "                yy = y**j\r\n",
    "                if yy > bound:\r\n",
    "                    break\r\n",
    "                if xx + yy <= bound:\r\n",
    "                    ans.add(xx+yy)\r\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound == 0:\n",
    "            return []\n",
    "        ans = set()\n",
    "        ln_x = [1]\n",
    "        ln_y = [1] \n",
    "        size = 0\n",
    "        while (x ** size <= bound - 1  and x != 1)or (y ** size <= bound -1 and y != 1):\n",
    "            if x ** size <= bound -1 :\n",
    "                ln_x.append(x ** size)\n",
    "            if y ** size <= bound -1 :\n",
    "                ln_y.append(y ** size)\n",
    "            \n",
    "            size += 1\n",
    "        \n",
    "        for i in ln_x:\n",
    "            for j in ln_y:\n",
    "                if i + j <= bound:\n",
    "                    ans.add(i+j)\n",
    "                else:\n",
    "                    break\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound < 2:\n",
    "            return []\n",
    "        elif x == 1 and y == 1:\n",
    "            return [2]\n",
    "        elif x == 1:\n",
    "            return [y ** i + 1 for i in range(int(math.log(bound, y)) + 1)]\n",
    "        elif y == 1:\n",
    "            return [x ** i + 1 for i in range(int(math.log(bound, x)) + 1)]\n",
    "\n",
    "        result = set()\n",
    "        for i in range(int(math.log(bound, x)) + 1):\n",
    "            j = 0\n",
    "            x_i = x ** i\n",
    "            while x_i + y ** j <= bound:\n",
    "                result.add(x_i + y ** j)\n",
    "                j += 1\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        resultList = set()\n",
    "        for i in range(21):\n",
    "            for j in range(21):\n",
    "                temp = pow(x, i) + pow(y, j)\n",
    "                if bound >= (temp):\n",
    "                    resultList.add(temp)\n",
    "        return list(resultList)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> list[int]:\n",
    "        ans = set()\n",
    "        a = 1\n",
    "        while a <= bound:\n",
    "            b = 1\n",
    "            while a + b <= bound:\n",
    "                ans.add(a + b)\n",
    "                b *= y\n",
    "                if(y == 1):\n",
    "                    break\n",
    "            a *= x\n",
    "            if(x == 1):\n",
    "                break\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        result = set()\n",
    "        i = 0\n",
    "\n",
    "        while x ** i <= bound:\n",
    "            j = 0\n",
    "            while x ** i + y ** j <= bound:\n",
    "                result.add(x ** i + y ** j)\n",
    "                j += 1\n",
    "                if y == 1:\n",
    "                    break\n",
    "            i += 1\n",
    "            if x == 1:\n",
    "                break\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        pow_y = 0\n",
    "        res = set()\n",
    "        tmp_y_val = pow(y , pow_y )\n",
    "        while tmp_y_val <= bound and pow_y <= 100:\n",
    "            pow_x = 0\n",
    "            tmp_x_val = pow(x, pow_x)\n",
    "            while tmp_y_val + tmp_x_val <= bound and pow_x <= 100:\n",
    "                res.add( tmp_x_val + tmp_y_val)\n",
    "                pow_x += 1\n",
    "                tmp_x_val = pow(x, pow_x)\n",
    "            pow_y += 1\n",
    "            tmp_y_val = pow(y , pow_y )\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        \n",
    "        res = []\n",
    "        px = 0\n",
    "        while x**px<bound:\n",
    "            py = 0\n",
    "            while x**px+y**py<=bound:\n",
    "                res.append(x**px+y**py)\n",
    "                py+=1\n",
    "                if y==1: break # y=1会导致内循环成死循环\n",
    "            px+=1\n",
    "            if x==1: break # x=1会导致外循环成死循环\n",
    "        return list(set(res)) #有重复的答案数组也很短，最后去重即可\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ans = set()\n",
    "        for i in range(0,20):\n",
    "            for j in range(0,20):\n",
    "                num = x**i+y**j\n",
    "                if num<=bound:\n",
    "                    ans.add(num)\n",
    "        return list(ans)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        a = 1\n",
    "        while a < bound:\n",
    "            b = 1\n",
    "            while a + b <= bound:\n",
    "                res.add(a + b)\n",
    "                b *= y\n",
    "                if y == 1:\n",
    "                    break\n",
    "            if x == 1:\n",
    "                break\n",
    "            a *= x\n",
    "        return list(res)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        s=set()\n",
    "        n=0\n",
    "       \n",
    "        for i in range(0,21):\n",
    "            for j in range(0,21):\n",
    "                n=x**i+y**j\n",
    "                if n<=bound:\n",
    "                    s.add(n)\n",
    "        return list(s)                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cal(x:int,y:int,bound:int):\n",
    "    i=0\n",
    "    res=[]\n",
    "    if(x==1):\n",
    "        res.append(y+1)\n",
    "        return res,1\n",
    "    while True:\n",
    "        tmp=x**i+y\n",
    "        if tmp>bound:\n",
    "            return res,i\n",
    "        res.append(tmp)\n",
    "        i+=1\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound<=1:\n",
    "            return []\n",
    "        res=[]\n",
    "        big,small=max(x,y),min(x,y)\n",
    "        tmp_res,num=cal(big,1,bound)\n",
    "        for i in range(num):\n",
    "            tm,t_tum=cal(small,big**i,bound)\n",
    "            for xx in tm:\n",
    "                if xx not in res:\n",
    "                    res.append(xx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        x_list = []\n",
    "        y_list = []\n",
    "        i, j= 0, 0\n",
    "        if x != 1:\n",
    "            while(x**i < bound):\n",
    "                x_list.append(x**i)\n",
    "                i += 1\n",
    "        else:\n",
    "            x_list = [1]\n",
    "        if y != 1:\n",
    "            while(y**j < bound):\n",
    "                y_list.append(y**j)\n",
    "                j += 1\n",
    "        else:\n",
    "            y_list = [1]\n",
    "            \n",
    "        nums = [x+y for x in x_list for y in y_list if x+y <= bound]\n",
    "\n",
    "        return list(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        x_pow = 1\n",
    "        x_base = x\n",
    "        y_pow = 1\n",
    "        y_base = y\n",
    "        x_subs = [1]\n",
    "        y_subs = [1]\n",
    "\n",
    "        while x < bound and x != 1:\n",
    "            x_subs.append(x)\n",
    "            x *= x_base\n",
    "        while y < bound and y != 1:\n",
    "            y_subs.append(y)\n",
    "            y *= y_base\n",
    "\n",
    "        results = set()\n",
    "        for xx in x_subs:\n",
    "            for yy in y_subs:\n",
    "                if xx + yy <= bound:\n",
    "                    results.add(xx + yy)\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        return list(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\r\n",
    "        ans = list()\r\n",
    "        i = 0\r\n",
    "        while x**i + 1 <= bound:\r\n",
    "            j = 0\r\n",
    "            while (z:=x**i + y**j) <= bound:\r\n",
    "                ans.append(z)\r\n",
    "                if y == 1:\r\n",
    "                    break\r\n",
    "                j +=1\r\n",
    "            if x == 1:\r\n",
    "                break\r\n",
    "            i += 1\r\n",
    "        return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        s=set()\n",
    "        n=0\n",
    "       \n",
    "        for i in range(0,21):\n",
    "            for j in range(0,21):\n",
    "                n=x**i+y**j\n",
    "                if n<=bound:\n",
    "                    s.add(n)\n",
    "        return list(s)                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        xs = [1]\n",
    "        ys = [1]\n",
    "        if x != 1:\n",
    "            while xs[-1] < bound:\n",
    "                xs.append(xs[-1] * x)\n",
    "        if y != 1:\n",
    "            while ys[-1] < bound:\n",
    "                ys.append(ys[-1] * y)\n",
    "\n",
    "\n",
    "        res = set()\n",
    "\n",
    "        # print(xs, ys)\n",
    "        for xx in xs:\n",
    "            for yy in ys:\n",
    "                n = xx + yy\n",
    "                if n <= bound:\n",
    "                    res.add(n)\n",
    "\n",
    "        return sorted(list(res))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        i=j=0\n",
    "        ans=[]\n",
    "        for i in range(100):\n",
    "            if(x**i>bound):break\n",
    "            for j in range(100):\n",
    "                if(y**j>bound):break\n",
    "                k=x**i+y**j\n",
    "                if(k<=bound and not k in ans):ans.append(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        value1 = 1\n",
    "        for i in range(21):\n",
    "            value2 = 1\n",
    "            for j in range(21):\n",
    "                value = value1 + value2\n",
    "                if value <= bound:\n",
    "                    res.add(value)\n",
    "                else:\n",
    "                    break\n",
    "                value2 *= y\n",
    "            if value1 > bound:\n",
    "                break\n",
    "            value1 *= x\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        value1 = 1\n",
    "        for i in range(21):\n",
    "            value2 = 1\n",
    "            for j in range(21):\n",
    "                value = value1 + value2\n",
    "                if value <= bound:\n",
    "                    res.add(value)\n",
    "                else:\n",
    "                    break\n",
    "                value2 *= y\n",
    "            if value1 > bound:\n",
    "                break\n",
    "            value1 *= x\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if x == 1 and y == 1:\n",
    "            if bound >= 2:\n",
    "                return [2]\n",
    "            else:\n",
    "                return []\n",
    "        a = 1\n",
    "        b = 1\n",
    "        x_times = 0\n",
    "        y_times = 0\n",
    "        if x > 1:\n",
    "            while a < bound:\n",
    "                a *= x\n",
    "                x_times += 1\n",
    "        else:\n",
    "            x_times = 1\n",
    "        if y > 1:\n",
    "            while b < bound:\n",
    "                b *= y\n",
    "                y_times += 1\n",
    "        else:\n",
    "            y_times = 1\n",
    "        a, b = 1, 1\n",
    "        result = set({})\n",
    "        for _ in range(x_times):\n",
    "            b = 1\n",
    "            for _ in range(y_times):\n",
    "                if a + b <= bound:\n",
    "                    result.add(a + b)\n",
    "                b *= y\n",
    "            a *= x\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound == 0:\n",
    "            return []\n",
    "        import math\n",
    "        result = set()\n",
    "        for i in range(21):\n",
    "            for j in range(21):\n",
    "                num = x**i + y**j\n",
    "                if num <= bound:\n",
    "                    result.add(num)\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        v1 = 1\n",
    "        v2 = 1\n",
    "        for i in range(21):\n",
    "            v2 = 1\n",
    "            for j in range(21):\n",
    "                value = v1 + v2\n",
    "                if value <= bound:\n",
    "                    res.add(value)\n",
    "                else:\n",
    "                    break\n",
    "                v2 *= y\n",
    "            v1 *= x\n",
    "            if v1 > bound:\n",
    "                break\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        list_ret = []\n",
    "        for i in range(0, 20):\n",
    "            for j in range(0, 20):\n",
    "                if x ** i + y ** j <= bound and (x ** i + y ** j) not in list_ret:\n",
    "                    list_ret.append(x ** i + y ** j)\n",
    "        list_ret.sort()\n",
    "        return list_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        i=0\n",
    "        j=0\n",
    "        Res=[]\n",
    "        while x**i+y**j<=bound:\n",
    "            print((i,j))\n",
    "            while x**i+y**j<=bound:\n",
    "                Res.append(x**i+y**j)\n",
    "                j+=1\n",
    "                if y==0 or y==1:\n",
    "                    break\n",
    "            j=0\n",
    "            i+=1\n",
    "            if x==0 or x==1:\n",
    "                break\n",
    "        return list(set(Res))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if x == 1:\n",
    "            xs = [1]\n",
    "        else:\n",
    "            now = 1\n",
    "            xs = []\n",
    "            while now <= bound:\n",
    "                xs.append(now)\n",
    "                now *= x\n",
    "        if y == 1:\n",
    "            ys = [1]\n",
    "        else:\n",
    "            now = 1\n",
    "            ys = []\n",
    "            while now <= bound:\n",
    "                ys.append(now)\n",
    "                now *= y\n",
    "        ans = []\n",
    "        for xi in xs:\n",
    "            for yi in ys:\n",
    "                if xi + yi <= bound:\n",
    "                    ans.append(xi + yi)\n",
    "                else:\n",
    "                    break\n",
    "        return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        value1 = 1\n",
    "        for i in range(21):\n",
    "            value2 = 1\n",
    "            for j in range(21):\n",
    "                value = value1 + value2\n",
    "                if value <= bound:\n",
    "                    res.add(value)\n",
    "                else:\n",
    "                    break\n",
    "                value2 *= y\n",
    "            if value1 > bound:\n",
    "                break\n",
    "            value1 *= x\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cal(x:int,y:int,bound:int):\n",
    "    i=0\n",
    "    res=[]\n",
    "    if(x==1):\n",
    "        res.append(y+1)\n",
    "        return res,1\n",
    "    while True:\n",
    "        tmp=x**i+y\n",
    "        if tmp>bound:\n",
    "            return res,i\n",
    "        res.append(tmp)\n",
    "        i+=1\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound<=1:\n",
    "            return []\n",
    "        res=[]\n",
    "        big,small=max(x,y),min(x,y)\n",
    "        tmp_res,num=cal(big,1,bound)\n",
    "        for i in range(num):\n",
    "            tm,t_tum=cal(small,big**i,bound)\n",
    "            for xx in tm:\n",
    "                if xx not in res:\n",
    "                    res.append(xx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound < 2:\n",
    "            return []\n",
    "        res = []\n",
    "        x1 = 1\n",
    "        y1 = 1\n",
    "        while x1 < bound:\n",
    "            while x1 + y1 <= bound:\n",
    "                a = x1 + y1\n",
    "                if a not in res:\n",
    "                    res.append(a)\n",
    "                y1 *= y\n",
    "                if y1 == 1:\n",
    "                    break\n",
    "            y1 = 1\n",
    "            x1 *= x\n",
    "            if x1 == 1:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = []\n",
    "        xlist, ylist = [], []\n",
    "        xa, yb = x ** 0, y ** 0\n",
    "        i, j = 0, 0\n",
    "        if x == 1 and x <= bound:\n",
    "            xlist.append(1)\n",
    "        else:\n",
    "            while xa <= bound:\n",
    "                xlist.append(xa)\n",
    "                i += 1\n",
    "                xa = x ** i\n",
    "        if y == 1 and y <= bound:\n",
    "            ylist.append(1)\n",
    "        else:\n",
    "            while yb <= bound:\n",
    "                ylist.append(yb)\n",
    "                j += 1\n",
    "                yb = y ** j\n",
    "\n",
    "        for a in xlist:\n",
    "            for b in ylist:\n",
    "                if a + b <= bound:\n",
    "                    res.append(a + b)\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound <= 1:\n",
    "            return []\n",
    "        if x == 1 and y == 1:\n",
    "            return [2]\n",
    "        elif x == 1 and y != 1:\n",
    "            return [1 + y ** _ for _ in range(1 + int(math.log(bound - 1, y)))]\n",
    "        elif x != 1 and y == 1:\n",
    "            return [x ** _ + 1 for _ in range(1 + int(math.log(bound - 1, x)))]\n",
    "        xmax = int(math.log(bound, x)) + 1\n",
    "        ymax = int(math.log(bound, y)) + 1\n",
    "\n",
    "        ans = []\n",
    "        for i in range(xmax):\n",
    "            for j in range(ymax):\n",
    "                n = x ** i + y ** j\n",
    "                if n <= bound and n not in ans:\n",
    "                    ans.append(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ans = set()\n",
    "        a = 1\n",
    "        while a <= bound:\n",
    "            b = 1\n",
    "            while a + b <= bound:\n",
    "                ans.add(a + b)\n",
    "                b *= y\n",
    "                if y == 1:\n",
    "                    break\n",
    "            if x == 1:\n",
    "                break\n",
    "            a *= x\n",
    "        return list(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        a=[1]\n",
    "        b=[1]\n",
    "        c=[]\n",
    "        m=x\n",
    "        n=y\n",
    "        while x<bound and x>1:\n",
    "            a.append(x)\n",
    "            x*=m\n",
    "        while y<bound and y>1:\n",
    "            b.append(y)\n",
    "            y*=n\n",
    "        for i in a:\n",
    "            for j in b:\n",
    "                m=i+j\n",
    "                if m<=bound:\n",
    "                    c.append(m)\n",
    "        return list(set(c))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound <2:\n",
    "            return []\n",
    "        if x == 1 and y == 1:\n",
    "    \n",
    "            return [2]\n",
    "        if x == 1:\n",
    "            a = [2]\n",
    "            z = y \n",
    "            while z < bound:\n",
    "                a.append(z+1)\n",
    "                z = z * y\n",
    "            return a\n",
    "        if y == 1:\n",
    "            a = [2]\n",
    "            z = x\n",
    "            while z < bound:\n",
    "                a.append(z+1)\n",
    "                z = z * x\n",
    "            return a\n",
    "        a,b = [1],[1]\n",
    "        z = x\n",
    "        while z < bound:\n",
    "            a.append(z)\n",
    "            z = z * x\n",
    "        z = y\n",
    "        while z < bound:\n",
    "            b.append(z)\n",
    "            z = z * y\n",
    "        d = {}\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                if a[i] + b[j] <= bound:\n",
    "                    d[a[i] + b[j]] = 1\n",
    "        out = list(d.keys())\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        i=j=0\n",
    "        ans=[]\n",
    "        for i in range(100):\n",
    "            if(x**i>bound):break\n",
    "            for j in range(100):\n",
    "                if(y**j>bound):break\n",
    "                if(x**i+y**j<=bound):ans.append(x**i+y**j)\n",
    "        return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        value1 = 1\n",
    "        ans = set()\n",
    "        for i in range(21):\n",
    "            value2 = 1\n",
    "            for j in range(21):\n",
    "                result = value1 + value2\n",
    "                if result <= bound:\n",
    "                    ans.add(result)\n",
    "                    value2 *= y\n",
    "                else:\n",
    "                    break\n",
    "            if value1 > bound:\n",
    "                break\n",
    "            else:\n",
    "                value1 *= x\n",
    "        return list(ans)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        final_list = []\n",
    "        for i in range(42):\n",
    "            for j in range(42):\n",
    "                result = x ** i + y ** j\n",
    "                if  result <= bound:\n",
    "                    if result in final_list:\n",
    "                        continue\n",
    "                    else:\n",
    "                        final_list.append(result)\n",
    "        final_list.sort()\n",
    "        return final_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res=[]\n",
    "        i_max=0\n",
    "        while x!=1 and x**i_max<=bound:\n",
    "            i_max += 1\n",
    "        j_max=0\n",
    "        while y!=1 and y**j_max <= bound:\n",
    "            j_max += 1\n",
    "        for i in range(0,i_max+1):\n",
    "            for j in range(0,j_max+1):\n",
    "                num=x**i + y**j\n",
    "                if num <= bound:\n",
    "                    res.append(num)\n",
    "                else:\n",
    "                    break\n",
    "        res=list(set(res))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        a = 1\n",
    "        while a <= bound:\n",
    "            b = 1\n",
    "            while a + b <= bound:\n",
    "                res.add(a + b)\n",
    "                if y == 1:\n",
    "                    break\n",
    "                b *= y\n",
    "            if x == 1:\n",
    "                break\n",
    "            a *= x\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        dp=[]\n",
    "        for i in range(21):\n",
    "            for j in range(21):\n",
    "                a=x**i+y**j\n",
    "                if x**i+y**j<=bound and a not in dp:\n",
    "                    dp.append(x**i+y**j)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ijbound = int(pow(bound, 1 / min(x, y)))\n",
    "        print(ijbound)\n",
    "        resultList = set()\n",
    "        for i in range(21):\n",
    "            for j in range(21):\n",
    "                temp = pow(x, i) + pow(y, j)\n",
    "                if bound >= (temp):\n",
    "                    resultList.add(temp)\n",
    "        return list(resultList)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        s=set()\n",
    "        n=0\n",
    "       \n",
    "        for i in range(0,21):\n",
    "            for j in range(0,21):\n",
    "                n=x**i+y**j\n",
    "                if n<=bound:\n",
    "                    s.add(n)\n",
    "        return list(s)                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        list_ret = []\n",
    "        for i in range(0, 20):\n",
    "            for j in range(0, 20):\n",
    "                if x ** i + y ** j <= bound and (x ** i + y ** j) not in list_ret:\n",
    "                    list_ret.append(x ** i + y ** j)\n",
    "        list_ret.sort()\n",
    "        return list_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ijbound = int(pow(bound, 1 / min(x, y)))\n",
    "        print(ijbound)\n",
    "        resultList = set()\n",
    "        for i in range(21):\n",
    "            for j in range(21):\n",
    "                temp = pow(x, i) + pow(y, j)\n",
    "                if bound >= (temp) and temp not in resultList:\n",
    "                    resultList.add(temp)\n",
    "        return list(resultList)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        lst=[]\n",
    "\n",
    "        \n",
    "        for i in range(100):\n",
    "            for j in range(100):\n",
    "                n = x**i+y**j\n",
    "                if n<=bound :\n",
    "                    lst.append(n)\n",
    "        return list(set(lst))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound < 2: return []\n",
    "        if x == y == 1: return [2]\n",
    "        ans = []\n",
    "        if x == 1:\n",
    "            tmp = 1\n",
    "            while tmp + 1 <= bound:\n",
    "                ans.append(tmp + 1)\n",
    "                tmp *= y\n",
    "            return ans\n",
    "        if y == 1:\n",
    "            tmp = 1\n",
    "            while tmp + 1 <= bound:\n",
    "                ans.append(tmp + 1)\n",
    "                tmp *= x\n",
    "            return ans\n",
    "        tmp0, res = 1, set()\n",
    "        while tmp0 + 1 <= bound:\n",
    "            tmp1 = 1\n",
    "            while tmp0 + tmp1 <= bound:\n",
    "                res.add(tmp0 + tmp1)\n",
    "                tmp1 *= y\n",
    "            tmp0 *= x\n",
    "        return [x for x in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound <= 1:\n",
    "            return []\n",
    "        i_max = floor(log(bound, x) + 1) if x != 1 else 1\n",
    "        j_max = floor(log(bound, y) + 1) if y != 1 else 1\n",
    "        ans = set()\n",
    "        for i in range(i_max):\n",
    "            for j in range(j_max):\n",
    "                tmp = x ** i + y ** j\n",
    "                if tmp <= bound:\n",
    "                    ans.add(tmp)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if bound < 2:\n",
    "            return []\n",
    "        elif x == 1 and y == 1:\n",
    "            return [2]\n",
    "        elif x == 1:\n",
    "            return [y ** i + 1 for i in range(int(math.log(bound, y)) + 1)]\n",
    "        elif y == 1:\n",
    "            return [x ** i + 1 for i in range(int(math.log(bound, x)) + 1)]\n",
    "\n",
    "        result = set()\n",
    "        for i in range(int(math.log(bound, x)) + 1):\n",
    "            j = 0\n",
    "            x_i = x ** i\n",
    "            while x_i + y ** j <= bound:\n",
    "                result.add(x_i + y ** j)\n",
    "                j += 1\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        n=0\n",
    "        m=0\n",
    "        o=[]\n",
    "        if bound<=1:return []\n",
    "        elif x==1 and y==1:\n",
    "            return [2]\n",
    "        elif x==1:\n",
    "            m=0\n",
    "            while y**m<=bound:\n",
    "                m=m+1\n",
    "                for i in range(m+1):\n",
    "                    if x+y**i not in o and x+y**i<=bound:\n",
    "                        o.append(x+y**i)\n",
    "            return o\n",
    "        elif y==1:\n",
    "            n=0\n",
    "            while x**n<=bound:\n",
    "                n=n+1\n",
    "                for i in range(n+1):\n",
    "                    if x**i+y not in o and x**i+y<=bound:\n",
    "                        o.append(x**i+y)\n",
    "            return o\n",
    "        else:\n",
    "            n=0\n",
    "            m=0\n",
    "            while x**n<=bound:\n",
    "                n=n+1\n",
    "            while y**m<=bound:\n",
    "                m=m+1\n",
    "            for i in range(m+1):\n",
    "                for j in range(n+1):\n",
    "                    if x**j+y**i not in o and x**j+y**i<=bound:\n",
    "                        o.append(x**j+y**i)\n",
    "            return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def powerfulIntegers(x: int, y: int, bound: int) -> List[int]:\n",
    "        import math\n",
    "        if bound ==0:\n",
    "            return []\n",
    "        if x != 1:\n",
    "            v1 = [x ** i for i in range(int(math.log(bound, x)) + 1)]\n",
    "        else:\n",
    "            v1 = [1]\n",
    "        if y != 1:\n",
    "            v2 = [y ** j for j in range(int(math.log(bound, y)) + 1)]\n",
    "        else:\n",
    "            v2 = [1]\n",
    "        v2.reverse()\n",
    "        i, j = 0, 0\n",
    "        ans = []\n",
    "        while 0 <= i < len(v1) and 0 <= j < len(v2):\n",
    "            if v1[i] + v2[j] <= bound:\n",
    "                if j > 0 and bound < v1[i] + v2[j - 1]:\n",
    "                    ans.extend([v1[i] + v2[k] for k in range(j, len(v2))])\n",
    "                    i += 1\n",
    "                elif j == 0:\n",
    "                    ans.extend([v1[i] + v2[k] for k in range(j, len(v2))])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j -= 1\n",
    "\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res=set()\n",
    "        a=1\n",
    "        while a<=bound:\n",
    "            b=1\n",
    "            while a+b<=bound:\n",
    "                res.add(a+b)\n",
    "                b*=y\n",
    "                if y==1:\n",
    "                    break\n",
    "            if x==1:\n",
    "                break\n",
    "            a*=x\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        a = 1\n",
    "        while a <= bound:\n",
    "            b = 1\n",
    "            while a + b <= bound:\n",
    "                res.add(a + b)\n",
    "                if y == 1:\n",
    "                    break\n",
    "                b *= y\n",
    "            if x == 1:\n",
    "                break\n",
    "            a *= x\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        a=[]\n",
    "        if x>y:\n",
    "            x,y=y,x\n",
    "        s=0\n",
    "        if x==1 and y==1 and bound>=2:\n",
    "            a.append(2)\n",
    "        elif bound<2:\n",
    "            return a\n",
    "        elif x==1:\n",
    "            while y**s<bound:\n",
    "                s+=1\n",
    "            for i in range(0,s):\n",
    "                if(y**i+1<=bound):\n",
    "                    a.append(y**i+1)\n",
    "        else:\n",
    "            while x**s<bound:\n",
    "                s+=1\n",
    "            for i in range(0,s):\n",
    "                for j in range(0,s):\n",
    "                    if(x**i+y**j<=bound):\n",
    "                        a.append(x**i+y**j)\n",
    "                    else:\n",
    "                        break\n",
    "        b=list(set(a))\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        i=j=0\n",
    "        ans=[]\n",
    "        for i in range(50):\n",
    "            if(x**i>bound):break\n",
    "            for j in range(50):\n",
    "                k=x**i+y**j\n",
    "                if(k>bound):break\n",
    "                if(not k in ans):ans.append(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(21):\n",
    "            for j in range(21):\n",
    "                a = pow(x,i) + pow(y,j)\n",
    "                if a <= bound and (a not in res):\n",
    "                    res.append(a)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if x==y==1 and bound>=2:\n",
    "            return [2]\n",
    "        if bound<2:\n",
    "            return []\n",
    "        a = 0\n",
    "        b = 0\n",
    "        \n",
    "        result = []\n",
    "        if x == 1:\n",
    "            while 1 + y**b<=bound:\n",
    "                z = 1 + y**b\n",
    "                result.append(z)\n",
    "                b = b+1\n",
    "            return result\n",
    "        if y == 1:\n",
    "            while 1 + x**a<=bound:\n",
    "                z = 1 + x**a\n",
    "                result.append(z)\n",
    "                a = a+1\n",
    "            return result\n",
    "\n",
    "        while x**a+y**b<=bound:\n",
    "            z = x**a+y**b\n",
    "            result.append(z)\n",
    "            b = b+1\n",
    "            if x**a+y**b>bound:\n",
    "                a = a+1\n",
    "                b = 0\n",
    "                if x**a+y**b>bound:\n",
    "                    return list(set(result))\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        s=set()\n",
    "        n=0\n",
    "       \n",
    "        for i in range(0,21):\n",
    "            for j in range(0,21):\n",
    "                n=x**i+y**j\n",
    "                if n<=bound:\n",
    "                    s.add(n)\n",
    "        return list(s)                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ans = set()\n",
    "        a = 1\n",
    "        while a <= bound:\n",
    "            b = 1\n",
    "            while a + b <= bound:\n",
    "                ans.add(a + b)\n",
    "                b *= y\n",
    "                if y == 1:\n",
    "                    break\n",
    "            if x == 1:\n",
    "                break\n",
    "            a *= x\n",
    "        return list(ans)\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/powerful-integers/solutions/2253040/python3javacgotypescript-yi-ti-yi-jie-ha-javr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        i=j=0\n",
    "        ans=[]\n",
    "        for i in range(100):\n",
    "            if(x**i>bound):break\n",
    "            for j in range(100):\n",
    "                if(y**j>bound):break\n",
    "                if(x**i+y**j<=bound):ans.append(x**i+y**j)\n",
    "        return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(100):\n",
    "            for j in range(100):\n",
    "                a = x**i\n",
    "                b = y**j\n",
    "                s = a + b\n",
    "                if s <= bound and s not in res:\n",
    "                    res.append(s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "            x_acc = 1\n",
    "            y_acc = 1\n",
    "            ans = []\n",
    "            while x_acc <= bound:\n",
    "                while y_acc <= bound - x_acc:\n",
    "                     ans.append(x_acc + y_acc)\n",
    "                     y_acc *=  y    \n",
    "                     if y == 1:\n",
    "                         break                 \n",
    "                y_acc = 1\n",
    "                if x == 1:\n",
    "                    break\n",
    "                x_acc *= x \n",
    "            \n",
    "            return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ans=set()\n",
    "        @lru_cache\n",
    "        def f(x,y,bound,i,j):\n",
    "            if x**i+y**j>bound:\n",
    "                return\n",
    "            ans.add(x**i+y**j)\n",
    "            f(x,y,bound,i+1,j)\n",
    "            f(x,y,bound,i,j+1)\n",
    "\n",
    "        @lru_cache\n",
    "        def g(z,bound,i):\n",
    "            if z**i+1>bound:\n",
    "                return\n",
    "            ans.add(z**i+1)\n",
    "            g(z,bound,i+1)\n",
    "        if x!=1 and y!=1:\n",
    "            f(x,y,bound,0,0)\n",
    "        if x==y==1:\n",
    "            return [2] if bound>=2 else []\n",
    "        else:\n",
    "            g(max(x,y),bound,0)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        ans = []\n",
    "        i = j = 0 \n",
    "        if x == 1 and y == 1 and bound <= 1:\n",
    "            return []\n",
    "        elif x == 1 and y == 1 and bound >1:\n",
    "            return [2]\n",
    "\n",
    "        if y == 1 and x != 1:\n",
    "            while x ** i <= bound:\n",
    "                temp = x ** i + 1\n",
    "                ans.append(temp)\n",
    "                i += 1\n",
    "        elif x == 1 and y != 1:\n",
    "            while y ** i <= bound:\n",
    "                temp = y ** i + 1\n",
    "                ans.append(temp)\n",
    "                i += 1\n",
    "        elif x == 1 and y == 1:\n",
    "            return []\n",
    "        else:\n",
    "            while x ** i <= bound:\n",
    "                while y ** j <= bound:\n",
    "                    temp = x ** i + y ** j\n",
    "                    if temp <= bound and temp not in ans:\n",
    "                        ans.append(temp)\n",
    "                    j += 1\n",
    "                    # print(temp)\n",
    "                i += 1\n",
    "                j = 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        for i in range(21):\n",
    "\n",
    "            for j in range(21):\n",
    "\n",
    "                if x**i + y**j <= bound:\n",
    "                    \n",
    "                    res.add(x**i + y**j)\n",
    "                else:\n",
    "                    break \n",
    "        # print(hash_table.values())\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        list_ret = []\n",
    "        for i in range(0, 20):\n",
    "            for j in range(0, 20):\n",
    "                if x ** i + y ** j <= bound and (x ** i + y ** j) not in list_ret:\n",
    "                    list_ret.append(x ** i + y ** j)\n",
    "        list_ret.sort()\n",
    "        return list_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\r\n",
    "        ans = set()\r\n",
    "        a = 1\r\n",
    "        while a + 1 <= bound:\r\n",
    "            b = 1\r\n",
    "            while a + b <= bound:\r\n",
    "                ans.add(a + b)\r\n",
    "                if y == 1:\r\n",
    "                    break\r\n",
    "                b *= y\r\n",
    "            if x == 1:\r\n",
    "                break\r\n",
    "            a *= x\r\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        # res=[]\n",
    "        # i=0\n",
    "        # while x**i<=bound:\n",
    "        #     j=0\n",
    "        #     while x**i+y**j<=bound:\n",
    "        #         res.append(x**i+y**j)\n",
    "        #         j+=1\n",
    "        #     i+=1\n",
    "        # return list(set(res))\n",
    "\n",
    "        def lt970_2(x,y,bound):\n",
    "\n",
    "            if bound<2:return []\n",
    "            if x==y==1:return [2] \n",
    "            if min(x,y)==1:\n",
    "                max_=max(x,y)\n",
    "                limit=int(math.log(bound,max_))\n",
    "                res=[]\n",
    "                for i in range(limit+1):\n",
    "                    if max_**i+1<=bound:res.append(max_**i+1)\n",
    "                    else:break\n",
    "                return res\n",
    "            else:\n",
    "                x_limit=int(math.log(bound,x))\n",
    "                res=set()\n",
    "                for i in range(x_limit+1):\n",
    "                    j=0\n",
    "                    while 1:\n",
    "                        temp=x**i+y**j\n",
    "                        if temp>bound:break\n",
    "                        if temp not in res:res.add(temp)\n",
    "                        j+=1\n",
    "                return list(res)\n",
    "\n",
    "\n",
    "        return lt970_2(x,y,bound)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        if x == 1 and y == 1:\n",
    "            return [2] if bound > 1 else []\n",
    "        if x == 1:\n",
    "            x = []\n",
    "            Y = 1\n",
    "            while Y < bound:\n",
    "                x.append(Y+1)\n",
    "                Y *= y\n",
    "            return x\n",
    "        if y == 1:\n",
    "            y = []\n",
    "            X = 1\n",
    "            while X < bound:\n",
    "                y.append(X+1)\n",
    "                X *= x\n",
    "            return y\n",
    "        jh = set()\n",
    "        X = 1\n",
    "        while X < bound:\n",
    "            Y = 1\n",
    "            while Y < bound:\n",
    "                if X+Y <= bound:\n",
    "                    jh.add(X+Y)\n",
    "                Y *= y\n",
    "            X *= x\n",
    "        return list(jh)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:\n",
    "        res = set()\n",
    "        value1 = 1\n",
    "        for i in range(21):\n",
    "            value2 = 1\n",
    "            for j in range(21):\n",
    "                value = value1 + value2\n",
    "                if value <= bound:\n",
    "                    res.add(value)\n",
    "                else:\n",
    "                    break\n",
    "                value2 *= y\n",
    "            if value1 > bound:\n",
    "                break\n",
    "            value1 *= x\n",
    "        return list(res)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
